/**
 * 使用条件
 * 1、Query Graph 的图编号是从1开始，如1、2、3、4……，而对Source Graph则对编号无要求
 * 2、
 * 
 */
package com.whu.gmatch;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.SimpleGraph;

public class MatchGraph {
	
	private  SimpleGraph<LabelVertex, LabelEdge> sourceGraph;
	private  Set<SimpleGraph<LabelVertex, LabelEdge>> queryGraphs;
	
	private SimpleGraph<LabelVertex, LabelEdge> qGraph;//query graph中的某一个
	private int qvCount;//query graph 中的某一个图节点的个数
	boolean flag;//source graph是否满足了某一个query graph
	
	private LabelVertex []qvertex;
	private LabelVertex [][]cvertex;//匹配节点集合
	private LabelVertex []f;//数组的下标代表 qid,数组内容表示在Source Graph中gid匹配边后对应的那个点
	private HashSet<Integer> visited;//标记source graph中的被访问过了的节点
	
	public MatchGraph(SimpleGraph<LabelVertex, LabelEdge> sourceGraph,
			Set<SimpleGraph<LabelVertex, LabelEdge>> queryGraphs){
		this.sourceGraph = sourceGraph;
		this.queryGraphs = queryGraphs;
	}
	
	public MatchGraph(SimpleGraph<LabelVertex, LabelEdge> sourceGraph,
			SimpleGraph<LabelVertex, LabelEdge> queryGraph){
		this.sourceGraph = sourceGraph;
		this.queryGraphs = new HashSet<SimpleGraph<LabelVertex, LabelEdge>>();
		this.queryGraphs.add(queryGraph);
	}
	
	boolean isMatch(){
		
		//记录source graph 中所有visited节点
		visited = new HashSet<Integer>();
		
		flag = false;
		
		Iterator<SimpleGraph<LabelVertex, LabelEdge>> qit = queryGraphs.iterator();		
		
		while(!flag && qit.hasNext()){
			qGraph = qit.next();
			qvCount = qGraph.vertexSet().size();
			
			qvertex = new LabelVertex[qvCount+1];//与节点编号一致,通过qid得到对应的qGraph
			cvertex = new LabelVertex[qvCount+1][];//匹配节点编号
			f = new LabelVertex[qvCount+1];//map节点编号
			
			for(LabelVertex sv :qGraph.vertexSet()){
				qvertex[sv.getId()]=sv;
			}
			
			for (LabelVertex qv : qGraph.vertexSet()) {
				String label = qv.getLabel();
				ArrayList<LabelVertex> tmp  = new ArrayList<LabelVertex>();
				for (LabelVertex sv : sourceGraph.vertexSet()) {
					if (sv.getLabel().equals(label)) {
						tmp.add(sv);
					}
				}
				cvertex[qv.getId()]=tmp.toArray(new LabelVertex[tmp.size()]);
			}

			recursiveSearch(qvertex[1]);// query中的第一个节点id,v1
		}
		
		if(flag){
			return true;
		}else{
			return false;
		}
		
	}
	
	public void recursiveSearch(LabelVertex qv) {
		if(flag){
			return;
		}
		
		int uid,qid=qv.getId();
		LabelVertex uv;
		for(int i=0;i<cvertex[qid].length;i++){
			uv = cvertex[qid][i];
			uid = uv.getId();
			if(!visited.contains(uid)){//未访问
				if(!matchable(qv, uv)){
					continue;
				}
				
				f[qid]=uv;
				visited.add(uid);
				if(qid < qvCount){
					recursiveSearch(qvertex[qid+1]);
				}else{
					for(int m=1;m<f.length;m++){
						System.out.print("("+f[m].getId()+":"+f[m].getLabel()+")  ");
					}
					System.out.println();
					
					flag = true;
					break;
				}
				
				f[qid]=null;
				visited.remove(uid);
			}
		}
	}
	
	public boolean matchable(LabelVertex qv,LabelVertex uv) {
		int qid = qv.getId();
				
		for(int i=1;i<qid;i++){//只考虑当前节点 和 那些qid之前已经处理过了的节点 之间的边	
			if(qGraph.containsEdge(qv,qvertex[i])){//查询图包含 qid-->i
				if(!sourceGraph.containsEdge(uv, f[i])){//测试：原图中是否包含 uid-->f(i),以此来判断uid是否是gid在原图中的映射
					return false;
				}
			}
		}
		
		return true;
	}
	
	//----------------------------test data----------------------------------
	private static SimpleGraph<LabelVertex, LabelEdge> loadSourceData(){

		SimpleGraph<LabelVertex, LabelEdge> g = new SimpleGraph<LabelVertex, LabelEdge>(
				LabelEdge.class);

		LabelVertex v1 = new LabelVertex(1, "A");
		LabelVertex v2 = new LabelVertex(2, "B");
		LabelVertex v3 = new LabelVertex(3, "C");
		LabelVertex v4 = new LabelVertex(4, "A");
		LabelVertex v5 = new LabelVertex(5, "B");
		LabelVertex v6 = new LabelVertex(6, "A");
		LabelVertex v7 = new LabelVertex(7, "C");
		LabelVertex v8 = new LabelVertex(8, "A");
		LabelVertex v9 = new LabelVertex(9, "C");
		LabelVertex v10 = new LabelVertex(10, "B");
		LabelVertex v11 = new LabelVertex(11, "A");
		LabelVertex v12 = new LabelVertex(12, "B");
//		LabelVertex v13 = new LabelVertex(13, "C");

		// add the vertices
		g.addVertex(v1);
		g.addVertex(v2);
		g.addVertex(v3);
		g.addVertex(v4);
		g.addVertex(v5);
		g.addVertex(v6);
		g.addVertex(v7);
		g.addVertex(v8);
		g.addVertex(v9);
		g.addVertex(v10);
		g.addVertex(v11);
		g.addVertex(v12);
//		g.addVertex(v13);

		// add edges to create a circuit
		g.addEdge(v1, v2);
		g.addEdge(v1, v3);
		g.addEdge(v2, v4);
		g.addEdge(v3, v4);
		g.addEdge(v3, v5);
		g.addEdge(v3, v6);
		g.addEdge(v5, v6);
		g.addEdge(v5, v7);
		g.addEdge(v5, v8);
		g.addEdge(v5, v9);
		g.addEdge(v7, v8);
		g.addEdge(v7, v9);
		g.addEdge(v7, v10);
		g.addEdge(v7, v11);
		g.addEdge(v10, v11);
		g.addEdge(v10, v12);
		
//		g.addEdge(v3,v13);
//		g.addEdge(v5, v13);
		return g;
	}

	private static SimpleGraph<LabelVertex, LabelEdge> loadQueryGraph() {
		SimpleGraph<LabelVertex, LabelEdge> g = new SimpleGraph<LabelVertex, LabelEdge>(
				LabelEdge.class);

		LabelVertex v1 = new LabelVertex(1, "A");
		LabelVertex v2 = new LabelVertex(2, "B");
		LabelVertex v3 = new LabelVertex(3, "C");
		LabelVertex v4 = new LabelVertex(4, "C");

		// add the vertices
		g.addVertex(v1);
		g.addVertex(v2);
		g.addVertex(v3);
		g.addVertex(v4);

		// add edges to create a circuit
		g.addEdge(v1, v2);
		g.addEdge(v1, v3);
		g.addEdge(v2, v3);
		g.addEdge(v2, v4);
		g.addEdge(v3, v4);

		return g;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MatchGraph mg = new MatchGraph(loadSourceData(),loadQueryGraph());
		if(mg.isMatch()){
			System.out.println("matched!");
		}else{
			System.out.println("unmatched!");
		}
	}

}
